
#pragma once
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <unordered_map>
#include <functional>
#include <iostream>
#include <assert.h>
using namespace std;

namespace matrix
{
    template <class V, class W, W MAX_W = INT64_MAX, bool Direction = false>
    class Graph
    {
        struct edge
        {
            size_t _srci; //起点下标
            size_t _dsti; //指向下标
            W _w;         //权值
            edge(size_t srci, size_t dsti, W w) : _srci(srci), _dsti(dsti), _w(w)
            {
            }
            bool operator>(const edge &e) const
            {
                return _w > e._w;
            }
        };

        typedef Graph<V, W, MAX_W, Direction> self;

    public:
        Graph() = default;
        Graph(const V *v, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(v[i]);
                _indexmap[v[i]] = i;
            }
            //为存储边的矩阵开辟空间
            _matrix.resize(n);
            for (size_t i = 0; i < _matrix.size(); i++)
            {
                _matrix[i].resize(n, MAX_W);
            }
        }

        //获取下标的接口
        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexmap.find(v);
            if (it != _indexmap.end())
            {
                return _indexmap[v];
            }
            else
            {
                std::cout << "不存在这样的节点" << std::endl;
                return -1;
            }
        }

        void addedge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            assert(srci != -1);
            assert(dsti != -1);
            _addedge(srci, dsti, w);
        }

        void Print()
        {
            //先打印顶点
            for (int i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]"
                     << "->" << _vertexs[i] << endl;
                ;
            }
            cout << endl;
            // 横下标
            cout << "  ";
            for (size_t i = 0; i < _vertexs.size(); ++i)
            {
                // cout << i << " ";
                printf("%4d", i);
            }
            cout << endl;
            for (size_t i = 0; i < _matrix.size(); ++i)
            {
                cout << i << " "; // 竖下标
                for (size_t j = 0; j < _matrix[i].size(); ++j)
                {
                    // cout << _matrix[i][j] << " ";
                    if (_matrix[i][j] == MAX_W)
                    {
                        // cout << "* ";
                        printf("%4c", '*');
                    }
                    else
                    {
                        // cout << _matrix[i][j] << " ";
                        printf("%4d", _matrix[i][j]);
                    }
                }
                cout << endl;
            }
            cout << endl;
        }
        void _BFS(size_t srci, vector<bool> &visited)
        {
            //遍历队列
            queue<int> q;
            q.push(srci);
            visited[srci] = true;
            int n = _vertexs.size();
            int num = 0;
            int size = 1;
            while (!q.empty())
            {
                cout << "第" << num << "层：" << endl;
                for (int i = 0; i < size; i++)
                {
                    int front = q.front();
                    q.pop();
                    cout << front << ":" << _vertexs[front] << " ";
                    for (int i = 0; i < n; i++)
                    {
                        if (_matrix[front][i] != MAX_W && !visited[i])
                        {
                            q.push(i);
                            visited[i] = true;
                        }
                    }
                    cout << endl;
                }
                num++;
                size = q.size();
            }
            cout << endl;
        }

        void BFS(const V &src)
        {

            //标记数组
            vector<bool> visited(_vertexs.size(), false);
            size_t srci = GetVertexIndex(src);
            _BFS(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (!visited[i])
                {
                    cout << endl;
                    _BFS(i, visited);
                }
            }
        }

        /*
                连通图的遍历
                void DFS(const V &src)
                {
                    size_t srci = GetVertexIndex(src);
                    vector<bool> visited(_vertexs.size(), false);
                    _DFS(srci, visited);
                    cout << endl;
                }

        */

        //非连通图的遍历
        void DFS(const V &src)
        {
            size_t srci = GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);
            _DFS(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (!visited[i])
                {
                    cout << endl;
                    _DFS(i, visited);
                }
            }
            cout << endl;
        }

    private:
        void _addedge(size_t srci, size_t dsti, const W &w)
        {
            _matrix[srci][dsti] = w;
            if (Direction == false)
            {
                _matrix[dsti][srci] = w;
            }
        }

        void _DFS(size_t srci, vector<bool> &visited)
        {
            cout << srci << ":" << _vertexs[srci] << " ";
            visited[srci] = true;
            for (int i = 0; i < _vertexs.size(); i++)
            {
                if (_matrix[srci][i] != MAX_W && !visited[i])
                {
                    _DFS(i, visited);
                }
            }
        }

    private:
        unordered_map<V, int> _indexmap; //记录顶点和下标的映射关系
        vector<V> _vertexs;              // 顶点集合的集合
        vector<vector<W>> _matrix;       // 存储边集合的矩阵
    };
}

namespace link_table
{

    template <class V, class W, W MAX_W = INT64_MAX, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, MAX_W, Direction> self;
        struct edge
        {
            //由于是链表，起点就是当前点，所以一般都省略
            // int _srci;
            size_t _dsti; //目标点
            W _w;         //权值

            //用一个链表将于该顶点相连的顶点连接起来
            edge *_next;
            edge(size_t dsti, const W &w)
                : _dsti(dsti), _w(w), _next(nullptr)
            {
            }
        };

    public:
        Graph() = default;
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            //添加顶点
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(a[i]);
                _indexmap[a[i]] = i;
            }
            _tables.resize(n, nullptr);
        }

        //获取顶点的下标
        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexmap.find(v);
            if (it != _indexmap.end())
            {
                return _indexmap[v];
            }
            else
            {
                std::cout << "不存在这样的节点" << std::endl;
                return -1;
            }
        }

        //添加边
        void addedge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            //头插的方式
            edge *head = _tables[srci];
            edge *eg = new edge(dsti, w);
            eg->_next = head;
            _tables[srci] = eg;
            //如果是无向图
            if (Direction == false)
            {
                edge *eg = new edge(srci, w);
                eg->_next = _tables[dsti];
                _tables[dsti] = eg;
            }
        }

        void Print()
        {
            //打印顶点
            for (size_t i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]"
                     << "->" << _vertexs[i] << endl;
            }

            //打印边
            for (size_t i = 0; i < _tables.size(); i++)
            {
                cout << _vertexs[i] << "[ " << i << "]->";
                edge *cur = _tables[i];
                while (cur)
                {
                    cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
                    cur = cur->_next;
                }
                cout << "nullptr" << endl;
            }
        }

    private:
        unordered_map<V, int> _indexmap; //记录顶点和下标的映射关系
        vector<V> _vertexs;              // 顶点集合的集合
        vector<edge *> _tables;          //邻接表
    };
};

